<!DOCTYPE html>



  


<html class="theme-next pisces use-motion" lang="zh-Hans">
<head>
  <!-- hexo-inject:begin --><!-- hexo-inject:end --><meta charset="UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1"/>
<meta name="theme-color" content="#222">









<meta http-equiv="Cache-Control" content="no-transform" />
<meta http-equiv="Cache-Control" content="no-siteapp" />
















  
  
  <link href="/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css" />







<link href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css" />

<link href="/css/main.css?v=5.1.3" rel="stylesheet" type="text/css" />


  <link rel="apple-touch-icon" sizes="180x180" href="/images/avatar.jpg?v=5.1.3">


  <link rel="icon" type="image/png" sizes="32x32" href="/images/avatar.jpg?v=5.1.3">


  <link rel="icon" type="image/png" sizes="16x16" href="/images/avatar.jpg?v=5.1.3">


  <link rel="mask-icon" href="/images/avatar.jpg?v=5.1.3" color="#222">





  <meta name="keywords" content="算法,Algorithms Notes,图," />










<meta name="description" content="无向图 图：是由一组顶点和一组能够将两个顶点相连的边组成的 自环：即可一条龙连接一个顶点和其自身的边 平行边：连接同一对顶点的两条边 常将含有平行边的图称为多重图，而没有平行边或自环的图称为简单图 相邻：当两顶点通过一条边相连时，称这两个顶点是相邻的，并称连接依附于这两个顶点 度数：顶点的度数就是依附于它的边数 子图：由所有边的一个子集以及这些边依附的所有顶点组成的图 路径是由边顺序连接的一系列顶">
<meta name="keywords" content="算法,Algorithms Notes,图">
<meta property="og:type" content="article">
<meta property="og:title" content="（四）图">
<meta property="og:url" content="http://fighterhit.github.io/2018/03/26/algorithm_and_datastructure/Algorithms4/Ch4-Graph/index.html">
<meta property="og:site_name" content="Fighter&#39;s Blog">
<meta property="og:description" content="无向图 图：是由一组顶点和一组能够将两个顶点相连的边组成的 自环：即可一条龙连接一个顶点和其自身的边 平行边：连接同一对顶点的两条边 常将含有平行边的图称为多重图，而没有平行边或自环的图称为简单图 相邻：当两顶点通过一条边相连时，称这两个顶点是相邻的，并称连接依附于这两个顶点 度数：顶点的度数就是依附于它的边数 子图：由所有边的一个子集以及这些边依附的所有顶点组成的图 路径是由边顺序连接的一系列顶">
<meta property="og:locale" content="zh-Hans">
<meta property="og:image" content="http://fighterhit.github.io/2018/03/26/algorithm_and_datastructure/Algorithms4/Ch4-Graph/无向图API.png">
<meta property="og:image" content="http://fighterhit.github.io/2018/03/26/algorithm_and_datastructure/Algorithms4/Ch4-Graph/邻接表数组.png">
<meta property="og:image" content="http://fighterhit.github.io/2018/03/26/algorithm_and_datastructure/Algorithms4/Ch4-Graph/典型Graph实现的性能复杂度.png">
<meta property="og:image" content="http://fighterhit.github.io/2018/03/26/algorithm_and_datastructure/Algorithms4/Ch4-Graph/图处理算法API.png">
<meta property="og:image" content="http://fighterhit.github.io/2018/03/26/algorithm_and_datastructure/Algorithms4/Ch4-Graph/图处理用例.png">
<meta property="og:image" content="http://fighterhit.github.io/2018/03/26/algorithm_and_datastructure/Algorithms4/Ch4-Graph/路径API.png">
<meta property="og:image" content="http://fighterhit.github.io/2018/03/26/algorithm_and_datastructure/Algorithms4/Ch4-Graph/连通分量.png">
<meta property="og:updated_time" content="2018-06-28T11:59:38.702Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="（四）图">
<meta name="twitter:description" content="无向图 图：是由一组顶点和一组能够将两个顶点相连的边组成的 自环：即可一条龙连接一个顶点和其自身的边 平行边：连接同一对顶点的两条边 常将含有平行边的图称为多重图，而没有平行边或自环的图称为简单图 相邻：当两顶点通过一条边相连时，称这两个顶点是相邻的，并称连接依附于这两个顶点 度数：顶点的度数就是依附于它的边数 子图：由所有边的一个子集以及这些边依附的所有顶点组成的图 路径是由边顺序连接的一系列顶">
<meta name="twitter:image" content="http://fighterhit.github.io/2018/03/26/algorithm_and_datastructure/Algorithms4/Ch4-Graph/无向图API.png">



<script type="text/javascript" id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/',
    scheme: 'Pisces',
    version: '5.1.3',
    sidebar: {"position":"left","display":"post","offset":12,"b2t":false,"scrollpercent":false,"onmobile":false},
    fancybox: true,
    tabs: true,
    motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
    duoshuo: {
      userId: '0',
      author: '博主'
    },
    algolia: {
      applicationID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    }
  };
</script>



  <link rel="canonical" href="http://fighterhit.github.io/2018/03/26/algorithm_and_datastructure/Algorithms4/Ch4-Graph/"/>





  <title>（四）图 | Fighter's Blog</title><!-- hexo-inject:begin --><!-- hexo-inject:end -->
  








</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="zh-Hans">

  
  
    
  

  <!-- hexo-inject:begin --><!-- hexo-inject:end --><div class="container sidebar-position-left page-post-detail">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta ">
    

    <div class="custom-logo-site-title">
      <a href="/"  class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">Fighter's Blog</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
      
        <p class="site-subtitle">深度沉迷学习</p>
      
  </div>

  <div class="site-nav-toggle">
    <button>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>

<nav class="site-nav">
  

  
    <ul id="menu" class="menu">
      
        
        <li class="menu-item menu-item-home">
          <a href="/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-home"></i> <br />
            
            首页
          </a>
        </li>
      
        
        <li class="menu-item menu-item-about">
          <a href="/about/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-user"></i> <br />
            
            关于
          </a>
        </li>
      
        
        <li class="menu-item menu-item-tags">
          <a href="/tags/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-tags"></i> <br />
            
            标签
          </a>
        </li>
      
        
        <li class="menu-item menu-item-categories">
          <a href="/categories/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-th"></i> <br />
            
            分类
          </a>
        </li>
      
        
        <li class="menu-item menu-item-archives">
          <a href="/archives/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-archive"></i> <br />
            
            归档
          </a>
        </li>
      

      
    </ul>
  

  
</nav>



 </div>
    </header>

    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          <div id="content" class="content">
            

  <div id="posts" class="posts-expand">
    

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://fighterhit.github.io/2018/03/26/algorithm_and_datastructure/Algorithms4/Ch4-Graph/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="Fighter.">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Fighter's Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">（四）图</h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2018-03-26T14:45:56+08:00">
                2018-03-26
              </time>
            

            

            
          </span>

          
            <span class="post-category" >
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/算法与数据结构/" itemprop="url" rel="index">
                    <span itemprop="name">算法与数据结构</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          
            <span class="post-meta-divider">|</span>
            <span class="page-pv"><i class="fa fa-file-o"></i>
            <span class="busuanzi-value" id="busuanzi_value_page_pv" ></span>
            </span>
          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        <h2 id="无向图"><a href="#无向图" class="headerlink" title="无向图"></a>无向图</h2><ul>
<li>图：是由一组顶点和一组能够将两个顶点相连的边组成的</li>
<li>自环：即可一条龙连接一个顶点和其自身的边</li>
<li>平行边：连接同一对顶点的两条边</li>
<li>常将含有平行边的图称为<strong>多重图</strong>，而没有平行边或自环的图称为<strong>简单图</strong></li>
<li>相邻：当两顶点通过一条边相连时，称这两个顶点是<strong>相邻</strong>的，并称连接<strong>依附于</strong>这两个顶点</li>
<li>度数：顶点的度数就是依附于它的边数</li>
<li>子图：由<strong>所有边的一个子集</strong>以及这些边<strong>依附的所有顶点</strong>组成的图</li>
<li>路径是由边顺序连接的一系列顶点；简单路径是一条没有重复顶点的路径</li>
<li>环是一条至少含有一条边且起点和终点相同的路径；简单环（除了起始和终点必须相同外）是一条不含有重复顶点和边的环</li>
<li>路径和环的长度为其中包含的边数</li>
<li>连通图：若从任意一个顶点都存在一条路径到达另一个任意顶点；非连通图：由若干连通部分组成，它们都是其极大连通子图</li>
<li><strong>树</strong>是无环连通图；互不相连的树组成的集合称为<strong>森林</strong>；<strong>连通图的生成树</strong>是它的一幅子图，它含有图中所有顶点且是一棵树；图的<strong>生成树森林</strong>是它的所有连通子图的生成树的集合</li>
<li>当且仅当V个结点的图G满足下列5个条件之一时是树<ul>
<li>G有V-1条边且不含环</li>
<li>G有V-1条边且是连通的</li>
<li>G是连通的，但删除任意一条边都会使它不再连通</li>
<li>G是无环图，但添加任意一条边都会产生一条环</li>
<li>G中任意一对顶点之间仅存在一条简单路径</li>
</ul>
</li>
<li><strong>二分图</strong>中每条边连接的两个顶点分别属于不同部分</li>
</ul>
<h3 id="图的数据结构"><a href="#图的数据结构" class="headerlink" title="图的数据结构"></a>图的数据结构</h3><img src="/2018/03/26/algorithm_and_datastructure/Algorithms4/Ch4-Graph/无向图API.png" title="无向图API">
<ol>
<li>必须为可能在应用中碰到的各种类型的图预留出足够<strong>空间</strong></li>
<li>Graph 实例方法的实现一定要快</li>
</ol>
<a id="more"></a>
<h3 id="三种图的表示方法："><a href="#三种图的表示方法：" class="headerlink" title="三种图的表示方法："></a>三种图的表示方法：</h3><ul>
<li>邻接矩阵：VxV 布尔矩阵，当顶点v和顶点w之间有相连的边时，定义v行w列元素值为true，否则为false。该方法不满足第一个条件，上百万顶点的图所需空间不能满足。（邻接矩阵也无法表示平行边）</li>
<li>边的数组：使用一个Edge类，含有两个int实例变量。该方法简洁但不满足第二个条件——查找结点的相邻结点需要检查图中所有边</li>
<li>邻接表数组：使用一个以顶点为索引的列表数组，其中每个元素都是和该顶点相邻的顶点列表。该数据结构能同时满足两个条件。</li>
</ul>
<img src="/2018/03/26/algorithm_and_datastructure/Algorithms4/Ch4-Graph/邻接表数组.png" title="邻接表数组">
<p>非稠密图标准表示称为<strong>邻接表</strong>，在该数据结构中每条边都会出现两次，其实现有如下性能：</p>
<ul>
<li>空间和V+E成正比</li>
<li>添加一条边所需时间为常数</li>
<li>遍历顶点v所有相邻顶点所需时间和v度数成正比（处理每个相邻顶点所需时间为常数）</li>
</ul>
<blockquote>
<p>当需要添加/删除顶点时，使用符号表（ST）来代替由顶点索引构成的数组；当需要删除一条边/检查图是否含有边v-w时，可以用SET代替Bag来实现邻接表。这种方法称为<strong>邻接集</strong>。</p>
</blockquote>
<img src="/2018/03/26/algorithm_and_datastructure/Algorithms4/Ch4-Graph/典型Graph实现的性能复杂度.png" title="典型Graph实现的性能复杂度">
<h3 id="图处理算法的设计模式"><a href="#图处理算法的设计模式" class="headerlink" title="图处理算法的设计模式"></a>图处理算法的设计模式</h3><p>图的表示和实现分离</p>
<img src="/2018/03/26/algorithm_and_datastructure/Algorithms4/Ch4-Graph/图处理算法API.png" title="图处理算法API">
<img src="/2018/03/26/algorithm_and_datastructure/Algorithms4/Ch4-Graph/图处理用例.png" title="图处理用例">
<h3 id="深度优先搜索（栈）"><a href="#深度优先搜索（栈）" class="headerlink" title="深度优先搜索（栈）"></a>深度优先搜索（栈）</h3><p>在访问其中任何一个顶点时：</p>
<ul>
<li>将它标记为已访问</li>
<li>递归地访问它所没有被标记过的邻居节点</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div></pre></td><td class="code"><pre><div class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">DepthFirstSearch</span> </span>&#123;</div><div class="line">    <span class="keyword">private</span> <span class="keyword">boolean</span>[] marked;</div><div class="line">    <span class="keyword">private</span> <span class="keyword">int</span> count;</div><div class="line"></div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="title">DepthFirstSearch</span><span class="params">(Graph G, <span class="keyword">int</span> s)</span> </span>&#123;</div><div class="line">        marked = <span class="keyword">new</span> <span class="keyword">boolean</span>[G.V()];</div><div class="line">        dfs(G, s);</div><div class="line">    &#125;</div><div class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">dfs</span><span class="params">(Graph g, <span class="keyword">int</span> v)</span> </span>&#123;</div><div class="line">        marked[v] = <span class="keyword">true</span>;</div><div class="line">        count++;</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> w : g.adj(v)) &#123;</div><div class="line">            <span class="keyword">if</span> (!marked[w]) &#123;</div><div class="line">                dfs(g, w);</div><div class="line">            &#125;</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">marked</span><span class="params">(<span class="keyword">int</span> w)</span> </span>&#123;</div><div class="line">        <span class="keyword">return</span> marked[w];</div><div class="line">    &#125;</div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">count</span><span class="params">()</span> </span>&#123;</div><div class="line">        <span class="keyword">return</span> count;</div><div class="line">    &#125;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
<blockquote>
<p>深度优先搜索标记与起点相连通的所有顶点所需时间和顶点度数之和成正比</p>
</blockquote>
<h3 id="寻找路径"><a href="#寻找路径" class="headerlink" title="寻找路径"></a>寻找路径</h3><img src="/2018/03/26/algorithm_and_datastructure/Algorithms4/Ch4-Graph/路径API.png" title="路径API">
<p>基于深度优先搜索查找路径（从给定起点s到它连通的所有顶点的路径）：</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div><div class="line">31</div><div class="line">32</div><div class="line">33</div><div class="line">34</div><div class="line">35</div><div class="line">36</div><div class="line">37</div><div class="line">38</div><div class="line">39</div><div class="line">40</div><div class="line">41</div></pre></td><td class="code"><pre><div class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">DepthFirstPaths</span> </span>&#123;</div><div class="line">    <span class="keyword">private</span> <span class="keyword">boolean</span>[] marked;</div><div class="line">    <span class="comment">/**</span></div><div class="line">     * 起点</div><div class="line">     */</div><div class="line">    <span class="keyword">private</span> <span class="keyword">final</span> <span class="keyword">int</span> s;</div><div class="line">    <span class="comment">/**</span></div><div class="line">     * 该顶点到一个顶点的已知路径上的最后一个顶点</div><div class="line">     */</div><div class="line">    <span class="keyword">private</span> <span class="keyword">int</span>[] edgeTo;</div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="title">DepthFirstPaths</span><span class="params">(Graph G, <span class="keyword">int</span> s)</span> </span>&#123;</div><div class="line">        marked = <span class="keyword">new</span> <span class="keyword">boolean</span>[G.V()];</div><div class="line">        edgeTo = <span class="keyword">new</span> <span class="keyword">int</span>[G.V()];</div><div class="line">        <span class="keyword">this</span>.s = s;</div><div class="line">        dfs(G, s);</div><div class="line">    &#125;</div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">hasPathTo</span><span class="params">(<span class="keyword">int</span> v)</span> </span>&#123;</div><div class="line">        <span class="keyword">return</span> marked[v];</div><div class="line">    &#125;</div><div class="line">    <span class="function"><span class="keyword">public</span> Iterable&lt;Integer&gt; <span class="title">pathTo</span><span class="params">(<span class="keyword">int</span> v)</span> </span>&#123;</div><div class="line">        <span class="keyword">if</span> (!hasPathTo(v)) &#123;</div><div class="line">            <span class="keyword">return</span> <span class="keyword">null</span>;</div><div class="line">        &#125;</div><div class="line">        <span class="comment">//注意使用了栈</span></div><div class="line">        Stack&lt;Integer&gt; path = <span class="keyword">new</span> Stack&lt;&gt;();</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> x = v; x != s ; x = edgeTo[x]) &#123;</div><div class="line">            path.push(x);</div><div class="line">        &#125;</div><div class="line">        path.push(s);</div><div class="line">        <span class="keyword">return</span> path;</div><div class="line">    &#125;</div><div class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">dfs</span><span class="params">(Graph g, <span class="keyword">int</span> v)</span> </span>&#123;</div><div class="line">        marked[v] = <span class="keyword">true</span>;</div><div class="line">        <span class="keyword">for</span> (Integer w : g.adj(v)) &#123;</div><div class="line">            <span class="keyword">if</span> (!marked[w])&#123;</div><div class="line">                edgeTo[w] = v;</div><div class="line"></div><div class="line">            &#125;</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
<blockquote>
<p>深度优先搜索得到从给定起点到任意标记顶点的路径所需时间和路径长度成正比</p>
</blockquote>
<h3 id="广度优先搜索（队列）"><a href="#广度优先搜索（队列）" class="headerlink" title="广度优先搜索（队列）"></a>广度优先搜索（队列）</h3><blockquote>
<p>单点最短路径。若s到v存在一条路径，找出最短那条（边数最少）。<br>要找到从s到v的最短路径，从s开始，在所有由一条边就可以到达的顶点中寻找v，若找不到则继续在与s距离两条边的所有顶点中查找v，如此一直进行。</p>
</blockquote>
<figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div><div class="line">31</div><div class="line">32</div><div class="line">33</div><div class="line">34</div><div class="line">35</div><div class="line">36</div><div class="line">37</div><div class="line">38</div><div class="line">39</div><div class="line">40</div><div class="line">41</div><div class="line">42</div><div class="line">43</div><div class="line">44</div><div class="line">45</div><div class="line">46</div><div class="line">47</div></pre></td><td class="code"><pre><div class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">BreadthFirstPaths</span> </span>&#123;</div><div class="line">    <span class="comment">/**</span></div><div class="line">     * 到达该店的最短路径是否已知</div><div class="line">     */</div><div class="line">    <span class="keyword">private</span> <span class="keyword">boolean</span>[] marked;</div><div class="line">    <span class="keyword">private</span> <span class="keyword">int</span>[] edgeTo;</div><div class="line">    <span class="keyword">private</span> <span class="keyword">final</span> <span class="keyword">int</span> s;</div><div class="line"></div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="title">BreadthFirstPaths</span><span class="params">(Graph G, <span class="keyword">int</span> s)</span> </span>&#123;</div><div class="line">        marked = <span class="keyword">new</span> <span class="keyword">boolean</span>[G.V()];</div><div class="line">        edgeTo = <span class="keyword">new</span> <span class="keyword">int</span>[G.V()];</div><div class="line">        <span class="keyword">this</span>.s = s;</div><div class="line">        bfs(G, s);</div><div class="line">    &#125;</div><div class="line">    <span class="comment">//非递归</span></div><div class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">bfs</span><span class="params">(Graph G, <span class="keyword">int</span> s)</span> </span>&#123;</div><div class="line">        Queue&lt;Integer&gt; queue = <span class="keyword">new</span> LinkedBlockingDeque&lt;&gt;();</div><div class="line">        marked[s] = <span class="keyword">true</span>;</div><div class="line">        queue.add(s);</div><div class="line">        <span class="comment">//一层一层遍历</span></div><div class="line">        <span class="keyword">while</span> (!queue.isEmpty()) &#123;</div><div class="line">            <span class="keyword">int</span> v = queue.poll();</div><div class="line">            <span class="keyword">for</span> (Integer w : G.adj(v)) &#123;</div><div class="line">                <span class="keyword">if</span> (!marked[w]) &#123;</div><div class="line">                    queue.add(w);</div><div class="line">                    edgeTo[w] = v;</div><div class="line">                    marked[w] = <span class="keyword">true</span>;</div><div class="line">                &#125;</div><div class="line">            &#125;</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">hasPathTo</span><span class="params">(<span class="keyword">int</span> v)</span> </span>&#123;</div><div class="line">        <span class="keyword">return</span> marked[v];</div><div class="line">    &#125;</div><div class="line">    <span class="function">Iterable&lt;Integer&gt; <span class="title">pathTo</span><span class="params">(<span class="keyword">int</span> v)</span> </span>&#123;</div><div class="line">        <span class="keyword">if</span> (!hasPathTo(v)) &#123;</div><div class="line">            <span class="keyword">return</span> <span class="keyword">null</span>;</div><div class="line">        &#125;</div><div class="line">        Stack&lt;Integer&gt; path = <span class="keyword">new</span> Stack&lt;&gt;();</div><div class="line">        path.push(v);</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> x = v; x != s; x = edgeTo[x]) &#123;</div><div class="line">            path.push(x);</div><div class="line">        &#125;</div><div class="line">        path.push(s);</div><div class="line">        <span class="keyword">return</span> path;</div><div class="line">    &#125;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
<blockquote>
<p>广度优先搜索所需时间在最坏情况下和 <code>V+E</code> 成正比</p>
</blockquote>
<p><a href="https://stackoverflow.com/questions/11468621/why-is-the-time-complexity-of-both-dfs-and-bfs-o-v-e" target="_blank" rel="noopener">Why is the time complexity of both DFS and BFS O( V + E )</a></p>
<h3 id="连通分量"><a href="#连通分量" class="headerlink" title="连通分量"></a>连通分量</h3><p>DFS可以应用找出一幅图所有连通分量</p>
<img src="/2018/03/26/algorithm_and_datastructure/Algorithms4/Ch4-Graph/连通分量.png" title="连通分量">
<figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div><div class="line">31</div><div class="line">32</div><div class="line">33</div><div class="line">34</div><div class="line">35</div></pre></td><td class="code"><pre><div class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">CC</span> </span>&#123;</div><div class="line">    <span class="keyword">private</span> <span class="keyword">boolean</span>[] marked;</div><div class="line">    <span class="keyword">private</span> <span class="keyword">int</span>[] id;</div><div class="line">    <span class="keyword">private</span> <span class="keyword">int</span> count;</div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="title">CC</span><span class="params">(Graph G)</span> </span>&#123;</div><div class="line">        marked = <span class="keyword">new</span> <span class="keyword">boolean</span>[G.V()];</div><div class="line">        id = <span class="keyword">new</span> <span class="keyword">int</span>[G.V()];</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> s = <span class="number">0</span>; s &lt; G.V(); s++) &#123;</div><div class="line">            <span class="keyword">if</span> (!marked[s]) &#123;</div><div class="line">                <span class="comment">//一次深度优先搜索就是一个连通分量</span></div><div class="line">                dfs(G, s);</div><div class="line">                count++;</div><div class="line">            &#125;</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">dfs</span><span class="params">(Graph g, <span class="keyword">int</span> s)</span> </span>&#123;</div><div class="line">        marked[s] = <span class="keyword">true</span>;</div><div class="line">        <span class="comment">//同一连通分量同一编号</span></div><div class="line">        id[s] = count;</div><div class="line">        <span class="keyword">for</span> (Integer v : g.adj(s)) &#123;</div><div class="line">            <span class="keyword">if</span> (!marked[v]) &#123;</div><div class="line">                dfs(g, v);</div><div class="line">            &#125;</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">count</span><span class="params">()</span></span>&#123;</div><div class="line">        <span class="keyword">return</span> count;</div><div class="line">    &#125;</div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">connected</span><span class="params">(<span class="keyword">int</span> w ,<span class="keyword">int</span> v)</span></span>&#123;</div><div class="line">        <span class="keyword">return</span> id[w] == id[v];</div><div class="line">    &#125;</div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">id</span><span class="params">(<span class="keyword">int</span> v)</span></span>&#123;</div><div class="line">        <span class="keyword">return</span> id[v];</div><div class="line">    &#125;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
<p>CC中基于DFS搜索解决图连通性问题相比：理论上，DFS 搜索比 union-find 快，因为它能保证所需时间是常数而 union-find 不行；但实际应用中，union-find 更快，因为它不需完整构造并表示一幅图。但DFS必须对图进行预处理，在只需判断连通性或只需完成大量连通性查询和插入操作混合等类似任务时，更倾向union-find，而DFS更适合实现抽象数据类型，它能更有效利用已有数据结构。</p>
<ul>
<li><p>使用深度优先搜索处理图的其它实例</p>
<ul>
<li><p>判断 G 是否为无环图</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div></pre></td><td class="code"><pre><div class="line"></div><div class="line"></div></pre></td></tr></table></figure>
</li>
<li><p>G 是二分图吗？（双色问题）</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div></pre></td><td class="code"><pre><div class="line"></div><div class="line"></div></pre></td></tr></table></figure>
</li>
</ul>
</li>
</ul>
<h2 id="有向图"><a href="#有向图" class="headerlink" title="有向图"></a>有向图</h2><h2 id="最小生成树"><a href="#最小生成树" class="headerlink" title="最小生成树"></a>最小生成树</h2><h2 id="最短路径"><a href="#最短路径" class="headerlink" title="最短路径"></a>最短路径</h2>
      
    </div>
    
    
    

    

    
      <div>
        <div style="padding: 10px 0; margin: 20px auto; width: 90%; text-align: center;">
  <div>请我喝杯咖啡吧☕~</div>
  <button id="rewardButton" disable="enable" onclick="var qr = document.getElementById('QR'); if (qr.style.display === 'none') {qr.style.display='block';} else {qr.style.display='none'}">
    <span>打赏</span>
  </button>
  <div id="QR" style="display: none;">

    
      <div id="wechat" style="display: inline-block">
        <img id="wechat_qr" src="/images/wechatpay.jpg" alt="Fighter. 微信支付"/>
        <p>微信支付</p>
      </div>
    

    
      <div id="alipay" style="display: inline-block">
        <img id="alipay_qr" src="/images/alipay.jpg" alt="Fighter. 支付宝"/>
        <p>支付宝</p>
      </div>
    

    

  </div>
</div>

      </div>
    

    
      <div>
        <ul class="post-copyright">
  <li class="post-copyright-author">
    <strong>本文作者：</strong>
    Fighter.
  </li>
  <li class="post-copyright-link">
    <strong>本文链接：</strong>
    <a href="http://fighterhit.github.io/2018/03/26/algorithm_and_datastructure/Algorithms4/Ch4-Graph/" title="（四）图">http://fighterhit.github.io/2018/03/26/algorithm_and_datastructure/Algorithms4/Ch4-Graph/</a>
  </li>
  <li class="post-copyright-license">
    <strong>版权声明： </strong>
    本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-nc-sa/3.0/" rel="external nofollow" target="_blank">CC BY-NC-SA 3.0</a> 许可协议。转载请注明出处！
  </li>
</ul>

      </div>
    

    <footer class="post-footer">
      
        <div class="post-tags">
          
            <a href="/tags/算法/" rel="tag"># 算法</a>
          
            <a href="/tags/Algorithms-Notes/" rel="tag"># Algorithms Notes</a>
          
            <a href="/tags/图/" rel="tag"># 图</a>
          
        </div>
      

      
      
      

      
        <div class="post-nav">
          <div class="post-nav-next post-nav-item">
            
              <a href="/2018/03/18/Java_Notes/JavaConcurrence/TheArtOfJavaConcurrency/Ch5-Java中的锁/" rel="next" title="Java中的锁">
                <i class="fa fa-chevron-left"></i> Java中的锁
              </a>
            
          </div>

          <span class="post-nav-divider"></span>

          <div class="post-nav-prev post-nav-item">
            
              <a href="/2018/03/29/other_notes/使用VSCode搭建C-C-开发环境/" rel="prev" title="使用VSCode搭建C/C++开发环境">
                使用VSCode搭建C/C++开发环境 <i class="fa fa-chevron-right"></i>
              </a>
            
          </div>
        </div>
      

      
      
    </footer>
  </div>
  
  
  
  </article>



    <div class="post-spread">
      
        <!-- JiaThis Button BEGIN -->
<div class="jiathis_style">
<span class="jiathis_txt">分享到：</span>
<a class="jiathis_button_fav">收藏夹</a>
<a class="jiathis_button_tsina">新浪微博</a>
<a class="jiathis_button_qzone">QQ空间</a>
<a class="jiathis_button_weixin">微信</a>
<a class="jiathis_button_cqq">腾讯QQ</a>
<a class="jiathis_button_copy">复制网址</a>
<a class="jiathis_button_share">一键分享</a>

<a href="http://www.jiathis.com/share?uid=2140465" class="jiathis jiathis_txt jiathis_separator jtico jtico_jiathis" target="_blank">更多</a>
<a class="jiathis_counter_style"></a>
</div>
<script type="text/javascript" >
var jiathis_config={
  data_track_clickback:true,
  summary:"",
  shortUrl:false,
  hideMore:false
}
</script>
<script type="text/javascript" src="http://v3.jiathis.com/code/jia.js?uid=" charset="utf-8"></script>
<!-- JiaThis Button END -->
      
    </div>
  </div>


          </div>
          


          
  
    <div class="comments" id="comments">
      <div id="lv-container" data-id="city" data-uid="MTAyMC8zMjY0Ni85MjA3"></div>
    </div>
  


        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    
    <div class="sidebar-inner">

      

      
        <ul class="sidebar-nav motion-element">
          <li class="sidebar-nav-toc sidebar-nav-active" data-target="post-toc-wrap">
            文章目录
          </li>
          <li class="sidebar-nav-overview" data-target="site-overview-wrap">
            站点概览
          </li>
        </ul>
      

      <section class="site-overview-wrap sidebar-panel">
        <div class="site-overview">
          <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
            
              <img class="site-author-image" itemprop="image"
                src="/images/avatar.jpg"
                alt="Fighter." />
            
              <p class="site-author-name" itemprop="name">Fighter.</p>
              <p class="site-description motion-element" itemprop="description">学习 | 分享 | 交流 | 进步</p>
          </div>

          <nav class="site-state motion-element">

            
              <div class="site-state-item site-state-posts">
              
                <a href="/archives/">
              
                  <span class="site-state-item-count">26</span>
                  <span class="site-state-item-name">日志</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-categories">
                <a href="/categories/index.html">
                  <span class="site-state-item-count">6</span>
                  <span class="site-state-item-name">分类</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-tags">
                <a href="/tags/index.html">
                  <span class="site-state-item-count">28</span>
                  <span class="site-state-item-name">标签</span>
                </a>
              </div>
            

          </nav>

          

          <div class="links-of-author motion-element">
            
              
                <span class="links-of-author-item">
                  <a href="https://github.com/fighterhit" target="_blank" title="GitHub">
                    
                      <i class="fa fa-fw fa-github"></i>GitHub</a>
                </span>
              
                <span class="links-of-author-item">
                  <a href="https://weibo.com/fighterhit" target="_blank" title="Weibo">
                    
                      <i class="fa fa-fw fa-weibo"></i>Weibo</a>
                </span>
              
            
          </div>

          
          

          
          

          

        </div>
      </section>

      
      <!--noindex-->
        <section class="post-toc-wrap motion-element sidebar-panel sidebar-panel-active">
          <div class="post-toc">

            
              
            

            
              <div class="post-toc-content"><ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#无向图"><span class="nav-number">1.</span> <span class="nav-text">无向图</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#图的数据结构"><span class="nav-number">1.1.</span> <span class="nav-text">图的数据结构</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#三种图的表示方法："><span class="nav-number">1.2.</span> <span class="nav-text">三种图的表示方法：</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#图处理算法的设计模式"><span class="nav-number">1.3.</span> <span class="nav-text">图处理算法的设计模式</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#深度优先搜索（栈）"><span class="nav-number">1.4.</span> <span class="nav-text">深度优先搜索（栈）</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#寻找路径"><span class="nav-number">1.5.</span> <span class="nav-text">寻找路径</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#广度优先搜索（队列）"><span class="nav-number">1.6.</span> <span class="nav-text">广度优先搜索（队列）</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#连通分量"><span class="nav-number">1.7.</span> <span class="nav-text">连通分量</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#有向图"><span class="nav-number">2.</span> <span class="nav-text">有向图</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#最小生成树"><span class="nav-number">3.</span> <span class="nav-text">最小生成树</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#最短路径"><span class="nav-number">4.</span> <span class="nav-text">最短路径</span></a></li></ol></div>
            

          </div>
        </section>
      <!--/noindex-->
      

      
      
    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright">&copy; 2016 - <span itemprop="copyrightYear">2018</span>
  <span class="with-love">
    <i class="fa fa-home"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">Fighter.</span>

  
</div>









        
<div class="busuanzi-count">
  <!--<script async src="https://dn-lbstatics.qbox.me/busuanzi/2.3/busuanzi.pure.mini.js"></script>-->
  <script async src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>

  
    <span class="site-uv">
      <i class="fa fa-user"></i>
      <span class="busuanzi-value" id="busuanzi_value_site_uv"></span>
      
    </span>
  

  
    <span class="site-pv">
      <i class="fa fa-eye"></i>
      <span class="busuanzi-value" id="busuanzi_value_site_pv"></span>
      
    </span>
  

    <span class="site-pv">&nbsp;&nbsp;&nbsp;|&nbsp;&nbsp;&nbsp;
    Hosted by <a target="_blank" href="https://github.com/">GitHub Pages</a>
    </span>

</div>







        
      </div>
    </footer>

    
      <div class="back-to-top">
        <i class="fa fa-arrow-up"></i>
        
      </div>
    

  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>









  












  
  <script type="text/javascript" src="/lib/jquery/index.js?v=2.1.3"></script>

  
  <script type="text/javascript" src="/lib/fastclick/lib/fastclick.min.js?v=1.0.6"></script>

  
  <script type="text/javascript" src="/lib/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script>

  
  <script type="text/javascript" src="/lib/velocity/velocity.min.js?v=1.2.1"></script>

  
  <script type="text/javascript" src="/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>

  
  <script type="text/javascript" src="/lib/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script>


  


  <script type="text/javascript" src="/js/src/utils.js?v=5.1.3"></script>

  <script type="text/javascript" src="/js/src/motion.js?v=5.1.3"></script>



  
  


  <script type="text/javascript" src="/js/src/affix.js?v=5.1.3"></script>

  <script type="text/javascript" src="/js/src/schemes/pisces.js?v=5.1.3"></script>



  
  <script type="text/javascript" src="/js/src/scrollspy.js?v=5.1.3"></script>
<script type="text/javascript" src="/js/src/post-details.js?v=5.1.3"></script>



  


  <script type="text/javascript" src="/js/src/bootstrap.js?v=5.1.3"></script>



  


  




	





  





  
    <script type="text/javascript">
      (function(d, s) {
        var j, e = d.getElementsByTagName(s)[0];
        if (typeof LivereTower === 'function') { return; }
        j = d.createElement(s);
        j.src = 'https://cdn-city.livere.com/js/embed.dist.js';
        j.async = true;
        e.parentNode.insertBefore(j, e);
      })(document, 'script');
    </script>
  








  





  

  
<script>
(function(){
    var bp = document.createElement('script');
    var curProtocol = window.location.protocol.split(':')[0];
    if (curProtocol === 'https') {
        bp.src = 'https://zz.bdstatic.com/linksubmit/push.js';        
    }
    else {
        bp.src = 'http://push.zhanzhang.baidu.com/push.js';
    }
    var s = document.getElementsByTagName("script")[0];
    s.parentNode.insertBefore(bp, s);
})();
</script><!-- hexo-inject:begin --><!-- hexo-inject:end -->


  

  
  


  

  

</body>
</html>
